Invariably, algorithms for joining spatial objects in a partitioned parallel environment are more complex than traditional algorithms for joining non-spatial objects. In order to support partitioned parallelism for spatial objects, a mechanism to partition input spatial data to the units of parallelism must be defined. There are three fundamental abstractions for spatial objects: point, line and polygon. Lines and polygons prevent the direct application of traditional partitioning algorithms to input spatial data because they represent extents in space. This characteristic of spatial data results in either a multidimensional representation or a linear transformation representation.
A typical partitioning mechanism for spatial data is based on space decomposition. Generally, space is decomposed into regions, the regions are assigned to the partitions (units of parallelism) and the spatial objects can be partitioned based on their relationship with the regions. For example, a region in a dynamic data structure such as an R-tree is a minimum bounding rectangle (MBR). In the R-tree, a spatial object is assigned or mapped to a single region, which satisfies some placement criteria, such as minimizing area expansion, region overlap, and the like. On the other hand, a partitioning mechanism using a static data structure such as an N×N grid provides a disjoint decomposition of space that may lead to spatial object duplication during the partitioning phase.
A spatial object's geometry is usually represented by a list of vertices, which represents a spatial object's position and shape in some N dimensional space. Typically, a spatial join of spatial objects is processed using a filter and refinement strategy. In the filter phase, an approximation of the spatial objects (MBR) is used to perform fast data preprocessing. In the refinement phase, the spatial objects' actual geometry is used to perform the final join process. There can be separate join algorithms for the filter phase and the refinement phase. An efficient filter join algorithm in the in memory plane sweep.
In view of the foregoing, conventional space decomposition does not provide a mechanism which may partition spatial objects to regions to avoid overlap and redundancy, facilitating even spatial distribution of input spatial data. Improvement in the spatial partitioning of input spatial data may improve significantly the spatial join of the partitioned spatial data.